package collection;

public class MyHashMap {
    private Entry[] data = new Entry[16];
    private static final float loadFator = 0.75f;
    private int size;

    public void put(String key, String value) {
        int hash = hash(key); //键的哈希值处理一下，使哈希值可以更加分散
        Entry e = new Entry(key, value, hash); //封装Entry对象
        putValue(data, e);  //在容量翻倍时，所有数据从新哈希，放入新数组时也要使用
        size++;            //放入数据后，数据量+1
        //数据量与容量的比值达到0.75，容量翻倍
        if (size / (float) data.length >= loadFator) {
            resize();
        }
    }

    public String get(String key) {
        int hash = hash(key);            //键的哈希值处理一下，使哈希值可以更加分散
        int index =  index(hash, data);  //计算加标
        Entry e = data[index];           //访问下标位置的节点
        if (e == null) {                 //没有数据返回null
            return null;
        }

        Entry tmp = e;                   //遍历链表
        while (tmp != null) {
            if (key.equals(tmp.key)) {   //找到相等的键
                return tmp.value;        //则返回对应的值
            }
            tmp = tmp.next;
        }

        return null;                     //找不到数据返回null
    }


    private void resize() {
        Entry[] tmp = new Entry[data.length<<1]; //翻倍长度的新数组

        for (Entry e : data) {  //原数组的数据进行遍历
            if (e == null) { //跳过空位置
                continue;
            }

            // 依次将链表的节点，放入新数组
            // n和nNext两个变量来回倒换，依次访问链表上的每个节点
            Entry n = e;
            while (n != null) {
                Entry nNext = n.next;
                n.next = null;      //节点断开连接
                putValue(tmp, n);   //并放入新数组
                n = nNext;
            }
        }

        this.data = tmp;
    }

    private void putValue(Entry[] tmp, Entry e) {
        int index = index(e.hash, tmp);
        if (tmp[index] == null) {
            tmp[index] = e;
        } else {
            Entry n = tmp[index];
            while (true) {
                if (n.key.equals(e.key)) {
                    n.value = e.value;
                    return;
                }

                if (n.next == null) {
                    n.next = e;
                    break;
                }

                n = n.next;
            }

        }
    }

    private int index(int hash, Entry[] tmp) {
        /*
            hash    0110111010111010000100110110101111
            length  0000000000000000001101001010010001   &
            ----------------------------------------------
                    0000000000000000000100000010000001
         */
        return hash & tmp.length-1;
    }

    private int hash(String key) {
        int hash = key.hashCode();
        // 模仿java.util.HashMap，对哈希值进行“扰动”（混杂、扰乱）
        hash = hash ^ (hash >>> 16);
        return hash;
    }


    class Entry {
        String key;
        String value;
        int hash;
        Entry next;
        Entry(String key, String value, int hash) {
            this.key = key;
            this.value = value;
            this.hash = hash;
        }
    }



    public static void main(String[] args) {
        MyHashMap m = new MyHashMap();
        //HashMap m = new HashMap();

        m.put("egw", "aaaa");
        m.put("bgerg", "bbb");
        m.put("cssfd", "ccccc");
        m.put("tyryre", "ddd");
        m.put("wewfs", "eee");
        m.put("egewg", "fff");
        m.put("uiuky", "ggg");
        m.put("rthr", "hhhhhh");
        m.put("wedvfw", "iiii");
        m.put("ytjt", "jjj");
        m.put("sdsdf", "sdsdf");
        m.put("kytukt", "kytukt");
        m.put("et5", "et5");
        m.put("gmtyj", "gmtyj");
        m.put("44", "44");
        m.put("rthr4y", "rthr4y");
        m.put("j56t4", "j56t4");
        m.put("g3rhh", "g3rhh");
        m.put("j56g3r", "j56g3r");
        m.put("rehrt5i5", "rehrt5i5");
        m.put("ethjtuk", "ethjtuk");
        m.put("erthyur", "erthyur");
        m.put("luikytjrh", "luikytjrh");


        System.out.println(m.get("j56t4"));
        System.out.println(m.get("kytukt"));
        System.out.println(m.get("luikytjrh"));
        System.out.println(m.get("wedvfw"));
    }
}
